package jalgebrava.group.algorithms.general;

import static jalgebrava.group.util.GroupMixins.*;
import jalgebrava.group.Group;
import jalgebrava.group.GroupElement;
import jalgebrava.group.Subgroup;
import jalgebrava.group.Subset;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.apache.log4j.Logger;

public class MinimalGeneratingSubset {
	private static Logger logger = Logger
			.getLogger(MinimalGeneratingSubset.class);

	public static final <G> Subset<G> minimalGeneratingSubset(Group<G> group) {

		Set<G> mgs = new HashSet<G>();
		Subgroup<G> generated = Subgroup.generate(new Subset<G>(group, mgs));

		logger.debug("mgs = " + mgs);
		logger.debug("generated = " + generated);

		for (GroupElement<G> x : elementsInDescendingOrder(group)) {
			logger.debug("Checking " + x);
			if (generated.contains(x.g)) {
				continue;
			}
			mgs.add(x.g);
			logger.debug("mgs = " + mgs);

			generated = Subgroup.generate(new Subset<G>(group, mgs));
			logger.debug("generated = " + generated);
			if (generated.size() == group.size()) {
				break;
			}
		}
		return new Subset<G>(group, mgs);
	}

	// < 1 not generating
	// == 1 perfect!
	// > 1 too much.
	private static final <G> double isStraightGeneratingSequence(Group<G> group,
			List<G> seq) {

		Set<G> generated = new HashSet<G>();
		generated.add(group.unit());
		
		
		for (G x : seq) {
			
			Set<G> newGenerated = new HashSet<G>();
			List<G> powers = Subgroup.powers(group, x);

			for (G a : generated) {
				for (G b : powers) {
					newGenerated.add(group.mul(a, b));
				}
			}
			generated = newGenerated;			

		}
		double defect = 1;
		for (G x: seq) {
			defect *= group.order(x);
		}
		return defect/group.size();
	}
}
